Syarikat ini ditubuhkan pada 27 Jun 1986 sebagai Highway Concessionnaires Berhad, ahli kumpulan syarikat United Engineers Malaysia Berhad (UEM).[3] Pada 13 Mei 1988, Highway Concessionaires Berhad bertukar nama kepada Projek Lebuhraya Utara Selatan Berhad (PLUS).[4] Pada 29 Januari 2002, PLUS Expressways Berhad (PEB) diperbadankan sebagai sebuah syarikat sendirian berhad.[5]

Lapan tahun kemudian, PLUS Malaysia Berhad (PMB) diperbadankan pada 29 November 2010 dan bergiat aktif dalam pegangan pelaburan.[6]

Pada 29 November 2011, PMB melengkapkan pemerolehan aset dan liabiliti PLUS Expressways Berhad. PMB menjadi syarikat pegangan Projek Lebuhraya Utara-Selatan Berhad (PLUS), Expressway Lingkaran Tengah Sdn Bhd (ELITE), Linkedua Malaysia Berhad (LINKEDUA), Konsortium Lebuhraya Butterworth-Kulim (KLBK) Sdn Bhd, Teras Teknologi Sdn Bhd (TERAS), PLUS Helicopter Services Sdn Bhd dan pemegang saham Touch 'n Go Sdn Bhd. Selain itu, PMB juga memperoleh Penang Bridge Sdn Bhd (PBSB) daripada UEM Builders Berhad.[6]

Projek Lebuhraya Usaha Sama Berhad (PLUS), anak syarikat PMB, diperbadankan pada 27 Julai 2011 untuk mengendalikan konsolidasi semua konsesi lebuhraya yang diperoleh di bawah satu entiti tunggal. Pemerolehan semua lima aset konsesi lebuhraya disiapkan 12 Januari 2012.[6]

Dengan pemrolehan tersebut, PMB merupakan pengendali tol lebuh raya terbesar di Malaysia dan salah satu yang terbesar di Asia Tenggara, Asia dan kelapan terbesar di dunia.[6]